package dp_algorithm.leetcode.hard;

/**
 * @author bruin_du
 * @description 正则表达式匹配
 * @date 2022/5/14 18:21
 **/
public class offer19_IsMatch {
    int choice = 1;
    public boolean isMatch(String s, String p) {
        if(choice == 1) {
            int row = s.length();
            int col = p.length();
            boolean[][] match = new boolean[row + 1][col + 1];
            match[0][0] = true;
            for (int j = 2; j <= col; j += 2) {
                match[0][j] = match[0][j - 2] && p.charAt(j - 1) == '*';
            }
            for (int i = 1; i <= row; i++) {
                for (int j = 1; j <= col; j++) {
                    if (p.charAt(j - 1) == '*') {
                        match[i][j] = match[i][j - 2] ||
                                match[i - 1][j] && (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.');
                    } else {
                        match[i][j] = match[i - 1][j - 1] && (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.');
                    }
                }
            }
            return match[row][col];
        }

        //方法二：递归法，不推荐
        if(choice == 2){
            return isMatchRecursion(s + "0",p + "0",0,0);
        }

        return false;
    }

    private boolean isMatchRecursion(String s, String p, int indexS, int indexP) {
        if(s.charAt(indexS) == '0' && p.charAt(indexP) == '0')
            return true;
        if(s.charAt(indexS) != '0' && p.charAt(indexP) == '0')
            return false;
        boolean b = s.charAt(indexS) == p.charAt(indexP) || (p.charAt(indexP) == '.' && s.charAt(indexS) != '0');
        if(p.charAt(indexP + 1) == '*'){
            if(b) {
                return isMatchRecursion(s,p,indexS + 1,indexP + 2) ||
                        isMatchRecursion(s, p, indexS, indexP + 2) ||
                        isMatchRecursion(s, p, indexS + 1, indexP);
            }else
                return isMatchRecursion(s,p,indexS,indexP + 2);
        }
        if(b)
            return isMatchRecursion(s, p, indexS + 1, indexP + 1);
        return false;
    }
}
